#include "Rse.h"
#include "Lse.h"


Rse::Rse(Tree* G, Distance* distance1)
{
	distance = distance1;
	ForestSize = new vector<int>[(G->getSize()+1)];
	Table= new vector<Tree*>[(G->getSize()+1)];
	inTree=G;
	Left_To_Right_Preorder_Traversal(G,true);
	find_Rse(G);
}

Rse::~Rse()
{
	delete []Table;
}

void Rse::Left_To_Right_Preorder_Traversal(Tree* G, bool restart)
{
	static int counter;
	if(restart)
		counter=0;
	if(G==NULL)
		return;
	G->getData()->setLTRP(counter++);
	for(int i=0; i<G->getChildrenCount() ; i++)
	{
		Left_To_Right_Preorder_Traversal(G->getChild(i) , false);
	}
}


void Rse::find_Rse(Tree* G)
{
	for (int i=G->getSize(); i>=0; i--)
	{
		currSize = G->getData()->getDT();
		DeleteLeftVertex(i,G);
		DeleteRightVertex(i,(G->getSize()+1)-i-(W.GetLeftTree()->getSize()+1));
	}
}

void Rse::DeleteLeftVertex(int i,Tree* G)//delete i Leftmost Vertexes
{
	if(i==0)
	{
		W.AddLeftTree(G);
		return;
	}
	currSize -= distance->DeleteNode(G);
	if(G->getLeft()==NULL)
	{
		Tree* temp;
		temp=W.GetLeftTree();
		W.RemoveLeftTree();
		DeleteLeftVertex(i-1,temp);
	}
	else
	{
		for(int index=G->getChildrenCount()-1; index>0 ; index--)
		{
			W.AddLeftTree(G->getChild(index));
		}
		DeleteLeftVertex(i-1,G->getLeft());
	}
}


void Rse::DeleteRightVertex(int i,int j)
{
	ForestSize[i].push_back(currSize);
	if(j==0)
	{
		Table[i].push_back(W.GetRightTree());
		W.RemoveLeftTree();  //remove the last tree in the forest W
	}
	else
	{
		currSize -= distance->DeleteNode(W.GetRightTree());
		Table[i].push_back(W.GetRightTree());
		if(W.GetRightTree()->getRight()==NULL)
		{
			W.RemoveRightTree();
			DeleteRightVertex(i,j-1);
		}
		else
		{
			Tree* temp=W.GetRightTree();
			W.RemoveRightTree();
			for(int index=0; index<temp->getChildrenCount() ; index++)
				W.AddRightTree(temp->getChild(index));
			DeleteRightVertex(i,j-1);
		}
	}
}

Tree* Rse::GetForest(int i, int j)
{
	return Table[i][j];
}

int Rse::get_JofI(int i)
{
	return inTree->getSize()-i-Table[i].back()->getSize();
}

int Rse::GetForestSize(int i, int j)
{
	return ForestSize[i][j];
}
